package Amazon;

public class ListLoop {

	public static class ListNode{
		public int value;
		public ListNode next;
		public ListNode(int x) {
			 value = x;
			 next = null;
		}
	
	}
	
	public static boolean hasLoops(ListNode myList){
		if(myList==null || myList.next==null) return false; //0 or 1 node, no loop
		ListNode slow = myList, fast = myList; //Two pointer, one slow, one fast
		while(fast!=null && fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;
			if(slow==fast) return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode l1 = new ListNode(1) ;
		ListNode l2 = new ListNode(2) ;	
		ListNode l3 = new ListNode(3) ;
		ListNode l4 = new ListNode(4) ;
		ListNode l5 = new ListNode(5) ;
		l1.next = l2;
//		l2.next = l3;
//		l3.next = l4;
//		l4.next = l5;
//		l5.next = null;
//		l5.next.next = null;
		boolean loop = hasLoops(l1);
		System.out.println(loop);
	}

}
